\documentclass[UTF8]{ctexart}
\usepackage{xltxtra}
\usepackage{geometry}
\usepackage{xcolor}
\usepackage{amsmath}
\usepackage{cases}
\usepackage{extarrows}
\usepackage{amsfonts}
\usepackage{longtable}
\usepackage{listings}
\usepackage{booktabs}
\usepackage{verbatim}
\usepackage{amssymb}
\usepackage{tabularray}
\geometry{a4paper, left=2cm, right=2cm, top=4cm, bottom=4cm}

\title{系统架构}
\author{Goodtea}
\date{}
\begin{document}  
  
\maketitle  

\section{思路}
\subsection{抽象树类}
\verb|BinaryTree|
$\to$\verb|BinarySearchTree|
$\to$\verb|BinaryTreeWithRotation|
$\to\begin{cases}\text{AvalTree}\\\text{RBT}\\\text{SplayTree}\end{cases}$

\subsubsection{基础虚类: BinaryTree} 

作为最顶级的基类, 用以规范全部二叉树的基本操作，涉及了下列关于树的基本操作：
\begin{lstlisting}[language=c++]
virtual const Comparable & findMin() const = 0;
virtual const Comparable & findMax() const = 0;
virtual bool contains(const Comparable & x) const = 0;
virtual bool isEmpty() const  = 0;
virtual void printTree(ostream & out = cout) const = 0;
virtual void makeEmpty() = 0;
virtual void insert(const Comparable & x) = 0;
virtual void insert(Comparable && x) = 0;
virtual void remove(const Comparable & x) = 0;

\end{lstlisting}

\subsubsection{BinaryTreeWithRotation} 

作为\verb|BinarySearchTree|的继承类, 用以规范全部涉及旋转操作的二叉树的基本操作：

\begin{lstlisting}[language=c++]
void rotateWithLeftChild(BinaryNode<Comparable> * & k2)
void rotateWithRightChild(BinaryNode<Comparable> * & k1)
void doubleWithLeftChild(BinaryNode<Comparable> * & k3)
void doubleWithRightChild(BinaryNode<Comparable> * & k1)
void reclaimMemory(BinaryNode<Comparable> *t)
\end{lstlisting}
\subsection{抽象节点类}
统一为\verb|class BinaryNode|，并设置以下public成员变量。
若不涉及到\verb|height|,\verb|color|操作时，这些变量设为默认值。
\begin{lstlisting}[language=c++]
template <typename Comparable>
class BinaryNode 
{
    enum {RED, BLACK};
    
    public:
        Comparable element;
        BinaryNode * left;
        BinaryNode * right;
        int height = 0;
        int color = 0;
};
    
\end{lstlisting}

\section{输出}
合并四个\verb|test.cpp|，测试代码(没有任何输出/报错即为成功)如下：
\begin{verbatim}
    1_Checking BinarySearchTree... (no more output means success)
    Finished BinarySearchTree testing
    2_Checking AvlTree... (no more output means success)
    Finished AvlTree testing
    3_Checking RedBlackTree (no more output means success)
    Finished RedBlackTree testing
    4_Checking RedBlackTree delete operation... (no more output means success)
    Finished RedBlackTree delete operation testing
    5_Checking SplayTree (no more output means success)
    Finished SplayTree testing
\end{verbatim}

\section{其他}
1. 在 RedBlackTree class 中实现了原文件中未实现的\verb|remove|函数并检查。

2. 本想添加\verb|find|函数以减少\verb|remove|和\verb|contains|函数段的代码冗余，但一直报错，故仍采用了原代码。
\end{document}  